package medium;

import java.util.Arrays;

/**
 * 3040. 相同分数的最大操作数目 II
 * 创建时间：2024/6/24 下午3:15
 * 给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：
 *
 * 选择 nums 中最前面两个元素并且删除它们。
 * 选择 nums 中最后两个元素并且删除它们。
 * 选择 nums 中第一个和最后一个元素并且删除它们。
 * 一次操作的 分数 是被删除元素的和。
 *
 * 在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
 *
 * 请你返回按照上述要求 最多 可以进行的操作次数。
 */
public class 相同分数的最大操作数目II_3040 {
    int[] nums;
    int[][] memo;
    public int maxOperations(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memo = new int[n][n];
        for (int[] x : memo) {
            Arrays.fill(x, -1);
        }
        int r1 = dfs(1, n - 2, nums[0] + nums[n - 1]); // 左右
        int r2 = dfs(2, n - 1, nums[0] + nums[1]);     // 最左
        int r3 = dfs(0, n - 3, nums[n - 2] + nums[n - 1]);  // 最右
        return Math.max(Math.max(r1, r2), r3) + 1;
    }

    public int dfs(int left, int right, int target) {
        if (left >= right) {
            return 0;
        }
        if (memo[left][right] != -1) {
            return memo[left][right];
        }
        int res = 0;
        if (nums[left] + nums[right] == target) {
            res = Math.max(res, dfs(left + 1, right - 1, target) + 1); // 左右
        }
        if (nums[left] + nums[left + 1] == target) {
            res = Math.max(res, dfs(left + 2, right, target) + 1);     // 最左
        }
        if (nums[right - 1] + nums[right] == target) {
            res = Math.max(res, dfs(left, right - 2, target) + 1);  // 最右
        }
        return  memo[left][right] = res;
    }
}
